// vim: foldmethod=marker : foldmarker=<<<,>>>
/*
 File: array.h
 Generated-From: array.nw
*/
#ifndef soddy_soddy_arrayH
#define soddy_soddy_arrayH

#include "lite/lite.h"

#define QSORT_THRESHOLD__soddy_array 7

#define ISORT_X1__soddy_array(tp,base,length,COMPARE,SWAP) \
 do {\
  is_t __relation; \
  tp __r; tp __l; tp __max; tp __base=base; i_t __length=length;\
  if (__length<2) break; \
  __r=__base+__length-1; \
  goto inside; do {\
   do { \
    __relation=COMPARE(__l,__max); \
    if (__relation>0) __max=__l;\
    __l++;\
    } while (__l<__r);\
   if (__max!=__r) SWAP(__max,__r); \
   __r--;\
   inside: __max=__r; __l=__base;\
   } while (__r>__l);\
  } while(0);

#define QSORT_X1__soddy_array(tp,a_base,a_length,COMPARE,SWAP) \
 do { \
  is_t __relation; i_t p1,p2;\
  tp __l; tp __r; tp __m;\
  struct { tp base; i_t length; } __frames[64], * __tos;\
\
  __tos=__frames; __frames[0].base=a_base; __frames[0].length=a_length;\
  while (__tos>=__frames) {\
   while (__tos->length>QSORT_THRESHOLD__soddy_array) {\
    __l=__tos->base;\
    __r=__tos->base+__tos->length-1;\
    __m=__tos->base+((__tos->length-1)>>1);\
\
    __relation=COMPARE(__l,__m); p1= __relation>0?1:0; \
    __relation=COMPARE(__l,__r); p2= __relation>0?1:0; \
    if (p1==p2) { /*left is not middle value*/\
     __relation=COMPARE(__m,__r); p2= __relation>0?1:0; \
     if (p1!=p2) __m=__r; /*right is middle value*/\
     SWAP(__l,__m); \
     };\
\
    p1=0; p2=0; __r=__tos->base+__tos->length;\
    goto insidefind;\
    do {\
     SWAP(__l,__r); \
     insidefind:\
     do { \
      __l++; p1++; \
      if (p1>=__tos->length) break;\
      __relation=COMPARE(__l,__tos->base);\
      } while (__relation<=0);\
     do { \
      __r--; p2++; \
      if (p2>=__tos->length) break;\
      __relation=COMPARE(__r,__tos->base);\
      } while (__relation>=0);\
     } while (__l<__r);\
    /*swap the leftest (middle) value with right pointer */\
    /*this put item in correct position*/\
    SWAP(__tos->base,__r); \
\
    if (p1<p2) { /*sort from 0 to qnt-p2*/ \
     __tos[1].base=__tos[0].base; __tos[1].length=__tos[0].length-p2; \
     __tos[0].base=__l; __tos[0].length-=p1;\
     __tos++;\
     }\
    else { /*sort from p1 to qnt*/\
     __tos[1].base=__l; __tos[1].length=__tos[0].length-p1; \
     __tos[0].length-=p2;\
     __tos++;\
     };\
    };\
\
   ISORT_X1__soddy_array(tp,__tos->base,__tos->length,COMPARE,SWAP); \
   __tos--;\
   }; \
  } while (0);

#endif
